---
title: "8、完美队列的数目"
created: 2025-11-28
tags:
  - 算法
---

# 8、完美队列的数目

## 题目 [完美队列的数目](https://www.lanqiao.cn/paper/3998/problem/3249/)

![[image-0f2988fb.png]]

## 思路分析

![[image-1046c8cb.png]]

双指针加快速幂

好离谱的地方就是 我双指针对撞指针的板子居然只能过60% 不如这个true时i++ false时j--快 没搞懂为什么 按道理应该是一样的吧

我真的很不理解 明明没走回头路 j是一直递减的 为什么效率会低一倍

chatgpt也讲不出哪里有问题

**第一段代码**中，通过固定`l`并向左移动`r`来减小和的策略本质上是利用了数组的有序性。`r`的移动是单向的，它不会重置或回头，这意味着它确实是高效的。每次当`l`向右移动时，因为数组是有序的，`l`的增大只会增加找到满足`a[l] + a[r] <= k`条件的难度，因此`r`可能需要进一步向左移动。

**第二段代码**中，策略基于`a[l] + a[r]`与`k`的比较来决定是增加`l`还是减少`r`。这种方法直接寻找满足条件的边界，同时避免了不必要的计算。当`a[l] + a[r] <= k`时，这意味着所有当前`l`到`r`之间的组合都是有效的，因此可以直接计算这些组合而不再单独检查。

### 性能差异的再分析：

在再次审视你的解释后，如果两段代码之间存在性能差异，这不应该是由于`r`回头移动导致的，因为在你的代码中`r`是单向移动的。

可能的性能差异原因包括：

**计算次数的差异**：第二种方法中，当找到满足条件的组合时，会立即计算从`l`到`r`的所有可能组合数量，然后`l++`或`r--`。这种方法可能在某些情况下减少了计算量，因为它立即利用当前的边界计算了所有有效的组合，而不是单独考虑每个`l`的位置。

**具体实现细节**：实际性能差异可能还受到编译器优化、具体实现的细节以及运行时环境的影响。例如，循环中的条件检查、函数调用的开销等，都可能对性能产生影响。

**代码逻辑的微小差异**：尽管两种策略在高层次上类似（都是利用双指针和有序数组的特性），但具体的实现逻辑（如何更新`l`和`r`、何时进行计算等）可能导致执行效率上的差异。

## 代码实现

9/15

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef long long LL;

const int N=1e5+10,mod=1e9+7;

int a[N];

LL qmi(LL a,int k){

    LL res=1%mod;

    while(k){

        if(k&1)

           res=res*a%mod;

        k>>=1;

        a=a*a%mod;

    }

    return res;

}

int main()

{

    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

   	int n,k;cin>>n>>k;

   	for(int i=0;i<n;i++)

	   cin>>a[i];

   	sort(a,a+n);

   	LL ans=0;

   	for(int l=0,r=n-1;l<=r;l++){

   		while(r>=l && a[l]+a[r]>k)

			r--;

		if(a[l]+a[r]<=k){

			ans=(ans+qmi(2,r-l))%mod;

		}

	}

   	cout<<ans;

    return 0;

}
```

ac

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef long long LL;

const int N=1e5+10,mod=1e9+7;

int a[N];

LL qmi(LL a,int k){

    LL res=1%mod;

    while(k){

        if(k&1)

           res=res*a%mod;

        k>>=1;

        a=a*a%mod;

    }

    return res;

}

int main()

{

    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

   	int n,k;cin>>n>>k;

   	for(int i=0;i<n;i++)

	   cin>>a[i];

   	sort(a,a+n);

   	LL ans=0;

   	for(int l=0,r=n-1;l<=r;){

		if(a[l]+a[r]<=k){

			ans=(ans+qmi(2,r-l))%mod;

			l++;

		}

		else

			r--;

	}

   	cout<<ans;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[7、基德的密码锁|7、基德的密码锁]] 🏠 [[00-刷题理模型]] ➡️ [[9、GCD王国和LCM王国|9、GCD王国和LCM王国]]